import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wangxin
 * Date: 2024-12-24
 * Time: 20:36
 */
public class MyLUCCache {
    static class DLinkNode{
        public int key;
        public int val;
        public DLinkNode prev;
        public DLinkNode next;

        public DLinkNode(){

        }
        public DLinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return "{" + "key=" + key +
                    ", val=" + val +"} ";
        }
    }
    public DLinkNode head;
    public DLinkNode tail;
    public int usedSize;
    public Map<Integer,DLinkNode> cache;
    public int capacity;
    public MyLUCCache(int capacity){
        this.capacity = capacity;
        this.head = new DLinkNode();
        this.tail = new DLinkNode();
        head.next = tail;
        tail.prev = head;
        cache = new HashMap<>();
    }

    public void put(int key,int val){
        DLinkNode node = cache.get(key) ;
          if (node == null){
              DLinkNode dLinkNode = new DLinkNode(key,val);
              cache.put(key,dLinkNode);
              insertTail(dLinkNode);
              usedSize++;
              if(usedSize > capacity){
                 DLinkNode remNode =  removeHead();
                  cache.remove(remNode.key);
                  usedSize--;
              }
              printNodes("put");
          }else{
              node.val = val;
              moveToTail(node);
          }
    }

    private void moveToTail(DLinkNode node) {
        removeNode(node);
        insertTail(node);
    }

    private void removeNode(DLinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insertTail(DLinkNode dLinkNode) {
       DLinkNode del =  tail.prev;
       del.next = dLinkNode;
       dLinkNode.prev = del;
       tail.prev = dLinkNode;
       dLinkNode.next = tail;

    }

    private DLinkNode removeHead() {
        DLinkNode del = head.next;
       head.next = del.next;
        del.next.prev = head;
        return del;
    }
    public int get(int key){
        DLinkNode node = cache.get(key);
        if(node == null){
            return -1;
        }
        moveToTail(node);
        printNodes("get");
        return node.val;
    }
    public void printNodes(String str){
        System.out.println(str+":");
        DLinkNode cur = head.next;
        while (cur != tail){
            System.out.print(cur);
            cur = cur.next;
        }
        System.out.println();
    }
}
